package binaryTree;

import java.util.Iterator;

import positionList.BoundaryViolationException;
import positionList.InvalidPositionException;
import positionList.NodePositionList;
import positionList.Position;
import positionList.PositionList;

/**
 * An implementation of the BinaryTree interface by means of a linked structure.
 */
public class LinkedBinaryTree<E> implements BinaryTree<E> {
	protected BTPosition<E> root; // reference to the root
	protected int size; // number of nodes

	/** Creates an empty binary tree. */
	public LinkedBinaryTree() {
		root = null; // start with an empty tree
		size = 0;
	}

	/** Returns the number of nodes in the tree. */
	public int size() {
		return size;
	}

	/** Returns whether a node is internal. */
	public boolean isInternal(Position<E> v) throws InvalidPositionException {
		checkPosition(v); // auxiliary method
		return (hasLeft(v) || hasRight(v));
	}

	/** Returns whether a node is the root. */
	public boolean isRoot(Position<E> v) throws InvalidPositionException {
		checkPosition(v);
		return (v == root());
	}

	/** Returns whether a node has a left child. */
	public boolean hasLeft(Position<E> v) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		return (vv.getLeft() != null);
	}

	/** Returns the root of the tree. */
	public Position<E> root() throws EmptyTreeException {
		if (root == null)
			throw new EmptyTreeException("The tree is empty");
		return root;
	}

	/** Returns the left child of a node. */
	public Position<E> left(Position<E> v) throws InvalidPositionException,
			BoundaryViolationException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> leftPos = vv.getLeft();
		if (leftPos == null)
			throw new BoundaryViolationException("No left child");
		return leftPos;
	}

	/** Returns the parent of a node. */
	public Position<E> parent(Position<E> v) throws InvalidPositionException,
			BoundaryViolationException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> parentPos = vv.getParent();
		if (parentPos == null)
			throw new BoundaryViolationException("No parent");
		return parentPos;
	}

	/** Returns an iterable collection of the children of a node. */
	public Iterable<Position<E>> children(Position<E> v)
			throws InvalidPositionException {
		PositionList<Position<E>> children = new NodePositionList<Position<E>>();
		if (hasLeft(v))
			children.addLast(left(v));
		if (hasRight(v))
			children.addLast(right(v));
		return children;
	}

	/** Returns an iterable collection of the tree nodes. */
	public Iterable<Position<E>> positions() {
		PositionList<Position<E>> positions = new NodePositionList<Position<E>>();
		if (size != 0)
			preorderPositions(root(), positions); // assign positions in
													// preorder
		return positions;
	}

	/** Returns an iterator of the elements stored at the nodes */
	public Iterator<E> iterator() {
		Iterable<Position<E>> positions = positions();
		PositionList<E> elements = new NodePositionList<E>();
		for (Position<E> pos : positions)
			elements.addLast(pos.element());
		return elements.iterator(); // An iterator of elements
	}

	/** Replaces the element at a node. */
	public E replace(Position<E> v, E o) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		E temp = v.element();
		vv.setElement(o);
		return temp;
	}

	// Additional accessor method
	/** Return the sibling of a node */
	public Position<E> sibling(Position<E> v) throws InvalidPositionException,
			BoundaryViolationException {
		BTPosition<E> vv = checkPosition(v);
		BTPosition<E> parentPos = vv.getParent();
		if (parentPos != null) {
			BTPosition<E> sibPos;
			BTPosition<E> leftPos = parentPos.getLeft();
			if (leftPos == vv)
				sibPos = parentPos.getRight();
			else
				sibPos = parentPos.getLeft();
			if (sibPos != null)
				return sibPos;
		}
		throw new BoundaryViolationException("No sibling");
	}

	// Additional update methods
	/** Adds a root node to an empty tree */
	public Position<E> addRoot(E e) throws NonEmptyTreeException {
		if (!isEmpty())
			throw new NonEmptyTreeException("Tree already has a root");
		size = 1;
		root = createNode(e, null, null, null);
		return root;
	}

	/** Inserts a left child at a given node. */
	public Position<E> insertLeft(Position<E> v, E e)
			throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> leftPos = vv.getLeft();
		if (leftPos != null)
			throw new InvalidPositionException("Node already has a left child");
		BTPosition<E> ww = createNode(e, vv, null, null);
		vv.setLeft(ww);
		size++;
		return ww;
	}

	/** Removes a node with zero or one child. */
	public E remove(Position<E> v) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		BTPosition<E> leftPos = vv.getLeft();
		BTPosition<E> rightPos = vv.getRight();
		if (leftPos != null && rightPos != null)
			throw new InvalidPositionException(
					"Cannot remove node with two children");
		BTPosition<E> ww; // the only child of v, if any
		if (leftPos != null)
			ww = leftPos;
		else if (rightPos != null)
			ww = rightPos;
		else
			// v is a leaf
			ww = null;
		if (vv == root) { // v is the root
			if (ww != null)
				ww.setParent(null);
			root = ww;
		} else { // v is not the root
			BTPosition<E> uu = vv.getParent();
			if (vv == uu.getLeft())
				uu.setLeft(ww);
			else
				uu.setRight(ww);
			if (ww != null)
				ww.setParent(uu);
		}
		size--;
		return v.element();
	}

	/** Attaches two trees to be subtrees of an external node. */
	public void attach(Position<E> v, BinaryTree<E> T1, BinaryTree<E> T2)
			throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		if (isInternal(v))
			throw new InvalidPositionException(
					"Cannot attach from internal node");
		int newSize = size + T1.size() + T2.size();
		if (!T1.isEmpty()) {
			BTPosition<E> r1 = checkPosition(T1.root());
			vv.setLeft(r1);
			r1.setParent(vv); // T1 should be invalidated
		}
		if (!T2.isEmpty()) {
			BTPosition<E> r2 = checkPosition(T2.root());
			vv.setRight(r2);
			r2.setParent(vv); // T2 should be invalidated
		}
		size = newSize;
	}

	/**
	 * If v is a good binary tree node, cast to BTPosition, else throw exception
	 */
	protected BTPosition<E> checkPosition(Position<E> v)
			throws InvalidPositionException {
		if (v == null || !(v instanceof BTPosition))
			throw new InvalidPositionException("The position is invalid");
		return (BTPosition<E>) v;
	}

	/** Creates a new binary tree node */
	protected BTPosition<E> createNode(E element, BTPosition<E> parent,
			BTPosition<E> left, BTPosition<E> right) {
		return new BTNode<E>(element, parent, left, right);
	}

	/**
	 * Creates a list storing the the nodes in the subtree of a node, ordered
	 * according to the preorder traversal of the subtree.
	 */
	protected void preorderPositions(Position<E> v,
			PositionList<Position<E>> pos) throws InvalidPositionException {
		pos.addLast(v);
		if (hasLeft(v))
			preorderPositions(left(v), pos); // recurse on left child
		if (hasRight(v))
			preorderPositions(right(v), pos); // recurse on right child
	}

	/** Returns whether the tree is empty. */
	public boolean isEmpty() {
		return size == 0;
	}

	/** Returns the right child of a node. */
	public Position<E> right(Position<E> v) throws InvalidPositionException,
			BoundaryViolationException { // metodo non implementato
		return null;
	}

	/** Returns whether a node has a right child. */
	public boolean hasRight(Position<E> v) throws InvalidPositionException { // metodo
																				// non
																				// implementato
		return false;
	}

	/** Returns whether a given node is external. */
	public boolean isExternal(Position<E> v) throws InvalidPositionException { // metodo
																				// non
																				// implementato
		return false;
	}

}
